package 爆刷leetcode.balabala.数独;

/**
 * @Author yaya
 * @Create 2024/5/27 21:25
 * Description:解数独
 */
public class SolveSudoku {

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };

        solveSudoku(board);
        System.out.println();

        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime + "ms");
    }

    public static void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
        for (char[] chars : board) {
            System.out.println();
            for (char c : chars) {
                System.out.print(c);
            }
        }
    }

    private static boolean solve(char[][] board) {
        // 遍历
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 未填入数字的格子
                if (board[i][j] == '.') {
                    // 检查1-9哪一个数字式合法的，合法则填入
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num;
                            // 递归确认上层的数字是否选的对。选不对设置成 . 并且回溯到上一层继续尝试
                            if (solve(board)) {
                                return true;
                            } else {
                                board[i][j] = '.'; // Backtrack
                            }
                        }
                    }
                    // 这一个格子无法找到合适的数，返回上一层并设置成 .
                    return false; // No valid number found, backtrack
                }
            }
        }
        return true; // All cells filled
    }

    // 判断是否合法
    private static boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) return false; // Check row
            if (board[i][col] == num) return false; // Check column
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) return false; // Check 3x3 grid
        }
        return true;
    }
}


